
import java.util.*;

// 点的实体类
class Point {
    double x, y;
    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

public class ClosestPoints {
    // 计算两点距离的平方（避免开根号，不影响大小比较）
    private static double distSq(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }

    // 暴力计算小规模点集的最近距离
    private static double bruteForce(Point[] points, int left, int right) {
        double min = Double.MAX_VALUE;
        for (int i = left; i <= right; i++) {
            for (int j = i + 1; j <= right; j++) {
                min = Math.min(min, distSq(points[i], points[j]));
            }
        }
        return min;
    }

    // 合并阶段：处理中间带的点
    private static double stripClosest(Point[] strip, int size, double d) {
        double min = d;
        // 按y坐标排序
        Arrays.sort(strip, 0, size, Comparator.comparingDouble(p -> p.y));
        // 每个点只比较后续6个点
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; j++) {
                min = Math.min(min, distSq(strip[i], strip[j]));
            }
        }
        return min;
    }

    // 分治递归函数
    private static double closestUtil(Point[] points, int left, int right) {
        // 终止条件：点集规模≤3，暴力计算
        if (right - left + 1 <= 3) {
            return bruteForce(points, left, right);
        }

        // 拆分：取中间点，分左右集
        int mid = (left + right) / 2;
        Point midPoint = points[mid];
        double dLeft = closestUtil(points, left, mid);
        double dRight = closestUtil(points, mid + 1, right);
        double d = Math.min(dLeft, dRight);

        // 提取中间带（x距离≤d的点）
        Point[] strip = new Point[right - left + 1];
        int stripSize = 0;
        for (int i = left; i <= right; i++) {
            if (Math.abs(points[i].x - midPoint.x) < d) {
                strip[stripSize++] = points[i];
            }
        }

        // 合并：计算中间带的最小距离
        return Math.min(d, stripClosest(strip, stripSize, d));
    }

    // 入口方法
    public static double closest(Point[] points) {
        // 先按x坐标排序
        Arrays.sort(points, Comparator.comparingDouble(p -> p.x));
        return Math.sqrt(closestUtil(points, 0, points.length - 1));
    }

    // 测试
    public static void main(String[] args) {
        Point[] points = {
                new Point(2, 3), new Point(12, 30),
                new Point(40, 50), new Point(5, 1),
                new Point(12, 10), new Point(3, 4)
        };
        System.out.println("最近点对距离：" + closest(points));
    }
}